package jm.algorithm.dp;

/**
 * @Description dp 最长共子串
 * @date 2022/5/25 9:11
 */
public class LCSString {

    public static void main(String[] args) {
        System.out.println(lcs2("ABCD","BABC"));
    }

    /**
     * dp 最长公共子串
     * @param str1
     * @param str2
     * @return
     */
    static int lcs(String str1, String str2){
        if (str1 == null || str2 == null) return 0;
        char[] c1  = str1.toCharArray();
        char[] c2  = str2.toCharArray();
        if (c1.length == 0 || c2.length == 0) return 0;

        int[][] dp = new int[c1.length + 1][c2.length + 1];
        int max = 0;
        for (int i = 1; i <= c1.length; i++) {
            for (int j = 1; j <= c2.length; j++) {
                if (c1[i - 1] != c2[j - 1]) continue;
                dp[i][j] = dp[i - 1][j -1] + 1;
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }

    /**
     * dp 最长公共子串 一维数组行列优化
     * @param str1
     * @param str2
     * @return
     */
    static int lcs2(String str1, String str2){
        if (str1 == null || str2 == null) return 0;
        char[] c1  = str1.toCharArray();
        char[] c2  = str2.toCharArray();
        if (c1.length == 0 || c2.length == 0) return 0;
        char[] rowStr = c1, colStr = c2;
        if (c1.length < c2.length){
            colStr = c1;
            rowStr = c2;
        }

        int[] dp = new int[colStr.length + 1];
        int max = 0;
        for (int i = 1; i <= rowStr.length; i++) {
            for (int j = 1; j <= colStr.length; j++) {
                if (rowStr[i - 1] != colStr[j - 1]) continue;
                dp[j] = dp[j -1] + 1;
                max = Math.max(max,dp[j]);
            }
        }
        return max;
    }
}
